#include "heap.h"

void HPInit(HP *php)
{
    assert(php);
    php->a = NULL;
    php->capacity = php->size = 0;
}
void HPDestroy(HP *php)
{
    assert(php);
    free(php->a);
    php->a = NULL;
    php->capacity = php->size = 0;
}
void Swap(HPDataType *a, HPDataType *b)
{
    HPDataType temp = *a;
    *a = *b;
    *b = temp;
}
void HPPush(HP *php, HPDataType x)
{
    assert(php);
    if (php->capacity == php->size)
    {
        size_t newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        HPDataType *newnode = (HPDataType *)realloc(php->a, sizeof(HPDataType) * newcapacity);
        if (newnode == NULL)
        {
            perror("newnode realloc : ");
            return;
        }
        php->a = newnode;
        php->capacity = newcapacity;
    }
    php->a[php->size] = x;
    php->size++;
    AdjustUp(php->a, php->size - 1);
}
void AdjustUp(HPDataType *a, int child)
{
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        if (a[child] > a[parent])
        {
            Swap(&a[child], &a[parent]);
            child = parent;
            parent = (parent - 1) / 2;
        }
        else
        {
            break;
        }
    }
}
void HPPop(HP *php)
{
    assert(php);
    assert(!HPEmpty(php));
    Swap(&php->a[0], &php->a[php->size - 1]);
    php->size--;
    AdjustDown(php->a, php->size, 0);
}
void AdjustDown(HPDataType *a, int n, int parent)
{
    int child = parent * 2 + 1;
    while (child < n)
    {
        if (child + 1 < n && a[child + 1] > a[child])
        {
            child++;
        }
        if (a[child] > a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = child * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
HPDataType HPTop(HP *php)
{
    assert(php);
    return php->a[0];
}
bool HPEmpty(HP *php)
{
    assert(php);
    return php->size == 0;
}
void HPInitArray(HP *php, HPDataType *a, int n)
{
    assert(php);
    php->a = (HPDataType *)malloc(sizeof(HPDataType) * n);
    if (php->a == NULL)
    {
        perror("php->a malloc :");
        return;
    }
    memcpy(php->a, a, sizeof(HPDataType) * n);
    php->capacity = php->size = n;
    ////向上排序 时间复杂度N*log N
    // for (int i = 1; i < php->size; i++)
    //{
    //	AdjustUp(php->a, i);
    // }
    // 向下排序,时间复杂度N
    for (int i = (php->size - 1) / 2; i >= 0; i--)
    {
        AdjustDown(php->a, php->size, i);
    }
}
void HeapSort(HPDataType *a, int n)
{
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(a, n, i);
    }
    int end = n - 1;
    while (end > 0)
    {
        Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        end--;
    }
}